
/**32. 最长有效括号
 * - 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度
 */
export function longestValidParentheses(s: string): number {
    //还是不理解
    //栈里不放字符，而是放字符的序号。匹配成功后，就用当前序减去字符序号，就是长度
    const stack = [-1] // 始终保持栈底元素为当前已经遍历过的元素中「最后一个没有被匹配的右括号的下标」
    let res = 0
    for (let i = 0; i < s.length; i++) {
        if (s[i] === '(') {
            stack.push(i)
        } else {
            stack.pop()//我们先弹出栈顶元素，“假设” 匹配了当前右括号

            if (stack.length === 0) {//如果栈为空，说明当前的右括号其实是没有被匹配的右括号，我们将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」
                stack.push(i)
            } else {//正常匹配成功
                res = Math.max(res, i - stack[stack.length - 1])
            }
        }
    }
    return res
}
/**232. 用栈实现队列 */
export function queueByStack() {
    class MyQueue {
        //用两个栈来模拟，一个进一个出
        private stackIn: number[]
        private stackOut: number[]
        constructor() {
            this.stackIn = [];
            this.stackOut = [];
        }
        //进队列
        push(x: number): void {
            this.stackIn.push(x)
        }
        //出队列
        pop(): number | undefined {
            //如果出站口为空的话，就先把进站口的数据 全部 放过来
            if (this.stackOut.length === 0) {
                while (this.stackIn.length > 0) {
                    this.stackOut.push(this.stackIn.pop()!);
                }
            }
            return this.stackOut.pop();
        }
        //返回队列开头的元素
        peek(): number | undefined {
            //复用代码，先把元素出队列，再放回去
            const temp = this.pop();
            if (temp) {
                this.stackOut.push(temp);
                return temp;
            } else {
                return undefined
            }
        }
        //判空
        empty(): boolean {
            return this.stackIn.length === 0 && this.stackOut.length === 0;
        }
    }
}
/**1047. 删除字符串中的所有相邻重复项
 * - 省流：开心消消乐
 * - 给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
 * - 在 S 上反复执行重复项删除操作，直到无法继续删除。 
 */
export function removeDuplicates(s: string): string {
    const stack: string[] = []
    for (let i = 0; i < s.length; i++) {
        const c = s[i];
        if (stack[stack.length - 1] === c) {
            stack.pop()
        } else {
            stack.push(c)
        }
    }
    return stack.join('')
}
/**1190. 反转每对括号间的子串
 * - https://leetcode.cn/problems/reverse-substrings-between-each-pair-of-parentheses/description/
 */
export function reverseParentheses(s: string): string {
    const stack: number[] = []
    const reverse = (arr: string[], left: number, right: number) => {
        while (left < right) {
            [arr[left], arr[right]] = [arr[right], arr[left]]
            left++; right--;
        }
    }
    /**存放 ( 的索引 */
    const strArr = s.split('')
    for (let i = 0; i < strArr.length; i++) {
        const c = strArr[i];
        if (c === '(') {
            stack.push(i)
        } else if (c === ')') {
            const left = stack.pop()!
            reverse(strArr, left, i)
        }
    }

    return strArr.filter(k => k !== '(' && k !== ')').join('')

}